\documentclass[hyperref,UTF8]{article}
\usepackage[colorlinks,linkcolor=blue,anchorcolor=yellow,citecolor=blue,urlcolor=blue]{hyperref}% set hyber link color as 'blue'
\usepackage{geometry}% adjust pdf page geometry
\usepackage{xcolor}% package to get color
\usepackage{graphicx}% package to insert figures
\usepackage{listings}% insert source codes using list
\usepackage{indentfirst}% zoom out at paragraph's fisrt line
\usepackage{float}% figure float effect
\usepackage{fancyhdr}% set the page upper and lower line style
\usepackage{amsmath}% insert Math functions 
\usepackage{caption} % caption for figures, auto number fig
\usepackage{CTEX}
\usepackage{enumerate}


\numberwithin{equation}{section} % number the equations according to section
\lstset{breaklines}
\lstset{extendedchars=false}%solve cross line equations
\geometry{b5paper,scale=0.85,centering} 
\pagestyle{fancy}
\setlength{\parindent}{2em} %zoom in at the start line
\title{\textit{Data Transfer Scheduling for Maximizing Throughput of Big-Data Computing in Cloud Systems} 读书笔记}
\author{谢正雄}
\date{\today}




\begin{document}\large %\Huge\huge\LARGE\Large\large\normalsize(default)\small\footnotesize\scriptsize\tiny 
	\maketitle{\Large}
	\thispagestyle{empty} % hide the page number of first title page
	\tableofcontents % generate content index
	
	
	\section{背景介绍}
		
		\subparagraph{时代背景}
		随着云计算技术的发展，越来越多的应用登上了云平台。为了处理这些大数据，许许多多的想法被提出然后实现，其中最常用的大数据框架之一自然是MapReduce，或者说Hadoop，这个框架的特点就是把数据分布到许多节点中经过处理再结合起来，这个框架经历了成千上万人的反复实验仍然屹立不倒，可以说是经历住了时间的考验，那么它真的这么完美吗？是否有改进的空间？本文从这个角度讨论本框架存在的一些可以改进的地方。
		
		\subparagraph{DCN(Data Center Networks)的数据调度问题}
		我们知道，Hadoop框架为了满足安全以及数据完整性的需要实现了数据冗余，也就是说，一份数据可能同时存在多个节点上，这样防止一个节点无法使用以后整个系统的崩坏；Hadoop还有一个特性就是数据处理的节点和存数据的节点并不总是相同，为了方便处理，通常在大数据应用里面是分开的，那么这里就会出现一个问题，就是数据传输的问题，数据该怎么从源节点来到处理节点，因为在复数数据节点的情况下，通路不只一条；结合前两个假设我们可以发现，这个调度问题就是一个多源的并行网络流问题，该怎么调度实现网络负载的利用最大化，感觉也是一个最大流问题。

		\paragraph{传统调度算法}

		\subparagraph{随机链路}
		从待选取的链路中随机选择一条，不考虑链路带宽和节点问题；一种思路但基本不用。

		\subparagraph{ECMP}
		Equal-Cost Multipath Routing算法，在多个相同节点的情况下，直接均分网络的负载到不同的通路上
		
		\subparagraph{VLB}
		Valiant Load Balancing算法，构建一个全连接的拓扑网络，当流来到第一个节点时，通过VLB网络内部的转发，将流量分摊给其他VLB节点，然后再从VLB网络的这些节点转发给主网络的其他节点，这样可以有效的降低单个节点的负担

		\subparagraph{缺陷}
		数据的传输往往是同时进行的，上述算法可以导致某些常用节点的链路过于拥挤，流可能富集在网络的某个或者某几个节点中，这样对网络的传输效率也是不好的；其实上述算法都是没有考虑到，数据节点重复性带来的优势，如果某个节点过于负担，可以从其他节点调取数据，本文就此方面提出了一些解决方案


		\begin{figure}[htbp]
			\centering
			\includegraphics{hdfs.png}
			\caption{HDFS 框架}
		\end{figure} 
		
	
		
	\section{方法介绍}
		\subparagraph{复杂度讨论}
		很显然这个问题是NP-hard问题，\textit{In an unsplittable flow problem, we have the additional restriction that each commodity must be routed on one path. All variants of this problem are NP-hard, but constant factor approximation algorithms exist for single-source multiple-sink variants.}也就是说可以通过求近似解的方式降低复杂度，本文从整数规划的角度尝试解决这个问题。

		\subparagraph{算法步骤}
		先把模型抽象成一种松弛型线性规划问题，然后用一些归化过程得到整数解，本文采用的应该是四舍五入法，最后算出每个通路的流量比率，得出整体调度；分析算法可以得出复杂度是多项式时间的，因为每一步都是多项式时间		

		


	\section{思想感悟}
		\subparagraph{优点}
		论文的思考方向非常有意思且非常有意义，首先是将数据的调度抽象化成一个多源并行网络流问题，而且从以前的论文上找到了相似的研究内容，并从论文内容中得到启发，将算法进行一定程度的改进放在Hadoop框架里面，让算法更加符合框架的运行结构；从模拟情况来看，算法的运行效率还算不错，测试结果也比较好，而且适用于复杂网络和简单网络。
		
	
		\subparagraph{缺点}
		类似HDFS的缺点，不支持对文件的随机写；不支持并发写入，同一个文件在同一时刻只能由一个客户端写入，不允许多个线程同时写，这虽然是为了安全考虑，但是也牺牲了一定性能；不适合低延时数据访问，延迟大可能是很难避免的一个问题，一旦需要数据传输，网络状态便成了模型的掣肘
	
	
	
	
	\begin{thebibliography}{l}
		
		\bibitem{cite1}{R. Xie and X. Jia, "Data Transfer Scheduling for Maximizing Throughput of Big-Data Computing in Cloud Systems," in IEEE Transactions on Cloud Computing, vol. 6, no. 1, pp. 87-98, 1 Jan.-March 2018, doi: 10.1109/TCC.2015.2464808.}
	\end{thebibliography}
\end{document}
